The video coding standard H.264/AVC is the latest video compression standard drafted by the Joint Video Team (JVT) established by the International Standardization Organization (ISO)/the International Electrotechnical Commission (IEC) and the International Telecommunication Union Telecommunication Standardization Sector (ITU-T). Compared with the preceding video compression standards, this standard has made remarkable improvements in the efficiency of video compression. Under the same Peak Signal to Noise Ratio (PSNR) quality, the code rate of H.264/AVC coder is reduced by approximately 50% compared with the code rate of MPEG-4 Advance Simple Profile (ASP).
In the design of H.264/AVC coder, a method of Rate Distortion Optimization (RDO) is adopted by both intra and inter predictions to perform decision. The object of introduction of this method is to select the best predictive mode from the possible combinations of all candidate predictive modes. The best coding mode selected based on rate distortion optimization means that in all possible mode combinations, a coding mode having the best video quality is selected in the condition of a given code rate, instead of simply minimizing the code rate or maximizing the video quality.
For an intra-4×4 prediction block, the best predictive mode corresponding to 16 pixels is determined by selecting the optimized rate distortion cost:RDCost_init=SSD(s,c,IMODE|Qp)+λMODE·R(s,c,IMODE|Qp)Wherein IMODE represents one of nine 4×4 block intra prediction modes; Qp represents the quantization parameter of a macro block; λMODE represents the Lagrange multiplier; R(·) represents the bit number of the selecting mode corresponding to the required coding; SSD(·) represents the sum of square of the difference between the original 4×4 luminance block s and the reconstructed block c corresponding to each of the candidate mode. Wherein:
      SSD    ⁡          (              s        ,        p            )        =            ∑              i        =        0            3        ⁢                  ⁢                  ∑                  j          =          0                3            ⁢                          ⁢                        (                                    s              ij                        -                          c              ij                                )                2            
In each computing process of SSD, cij is a reconstructed pixel value after being transformed, quantified, inversely quantified and inversely transformed. This means that the corresponding subblock is required to be coded each time when a to candidate mode is detected. The Discrete Cosine Transform (DCT), quantification and computing of entropy coding are very complex. Before the best predictive mode combination of a macro block is determined, the rate distortion cost for the combination of all chromaticity components and luminance components in the macro block should be repeatedly computed, that is, M8×(M4×16+M16), wherein is M8, M4 and M16 respectively represent the mode number of the chroma block prediction, the luminance block I4MB (intra-frame macro block 4×4 luminance manner) prediction and the I16MB (intra-frame macro block 16×16 luminance manner) prediction. This means that the rate distortion optimization process of a macro block should be computed 4×(9×16+4)=592 times, which results in that the complexity of the algorithm of the H.264 coder sharply increases. Thus, it is hard to apply this compression standard to a real time system with a low complexity processing capability, e.g. a mobile device.
In order to solve this problem, JM6.1d provides a new rate distortion cost function to improve the coding performance:RDCost—SAD=SAD(s,p)+4P·λMODE Wherein the Sum of Absolute Differences (SAD) is computed by using the following formula:
      SAD    ⁡          (              s        ,        p            )        =            ∑              i        =        0            3        ⁢                  ⁢                  ∑                  j          =          0                3            ⁢                          ⁢                                            s            ij                    -                      p            ij                                      Wherein pij is the (i, j)th element in the predictive block. When the predictive mode is the same as the most probable predictive mode, the factor P equals to 0, otherwise, it equals to 1 with respect to other modes.
This cost function greatly reduces the complexity of computing. However, since the SAD-based rate distortion cost function RDCost_SAD neglects the effect of the code rate, the SAD-based rate distortion cost RDCost_SAD is more different from the selected result of the cost value RDCost_init in the original rate distortion optimization model. Particularly, when comparing nine modes, if there is a trivial difference between the minimum SAD value and the second minimal SAD value, and the code rate corresponding to the minimum SAD is comparatively big, after multiplying with the constant coefficient λMODE, the mode selected by the original rate distortion optimization model will be different from the mode selected by the SAD-based rate distortion cost.
Meanwhile, the domestic and foreign scholars and researchers also propose some fast algorithms for the intra prediction mode determination in H.264/AVC. F. Pan et al. have proposed a rapid mode selecting algorithm based on local edge information. The local edge map of the block to be coded is determined by means of the Sobel operator, and corresponding edge histogram map is established, so, the rate distortion optimization cost is computed by selecting a mode based on the proximal edge direction.
C. C. Cheng has proposed a three-step rapid algorithm for the intra-4×4 prediction block. In the algorithm, in the first step, three most probable modes are initially compared, and they are the horizontal mode, the perpendicular mode and the Direct Coefficient (DC) mode respectively. In the second step, based on the probable mode determined in the first step, two modes at the adjacent directions are selected for further refining the direction. Finally, the rate distortion costs of all modes after the refinement are computed to determine the final mode.
C. S. Kim has proposed a solution of synthetically considering the characteristics of the target block spatial domain and the transform domain, and filtering out most of candidate modes by analyzing the relationship between the posterior error probability and average rate-distortion loss.
The main idea of theses methods is to select a mode in which is most relative with the gray direction in the block to be predicted. From the view of essence, it is to look for a mode having the minimum SAD compared with the block to be coded from the nine candidate predictive mode blocks, but the effect of the code rate in the rate distortion optimization cost function is not considered. In order to avoid the error caused by merely considering SAD, these rapid algorithms during designing usually rely on selecting much more candidate modes, e.g. two modes at the adjacent directions of the modes corresponding to the minimum SAD and DC mode, to compute the rate distortion optimization cost.